\section{Heurística de Búsqueda Local}
\subsection{Introducción}

La idea del algoritmo de búsqueda local es partir de una solución válida e intentar mejorarla a través de operaciones para acercarse lo más posible a la solución óptima. Para ver qué operaciones vamos a aplicar, tenemos que establecer una ``vecindad''. Además, las operaciones que vamos realizando siempre buscan mejorar lo que teníamos previamente. Si no tenemos una solución mejor, es porque llegamos a un mínimo local y nos quedamos allí. Este método me asegura avanzar hasta un mínimo local con un ``bajo costo'' pero ese mínimo puede estar muy lejos de el mínimo global, al cual nunca voy a poder llegar ya que no se me permite hacer operaciones que empeoren la solución previa y así salir de esa área local.

\subsection{Desarrollo}
En nuestro ejercicio, establecemos la vecindad entre dos soluciones cuando difieren en exactamente dos ejes. Es decir, puedo pasar de una solución a una vecina sacando un nodo cualquiera (distinto del origen) y ponerlo entre otros dos cualesquiera. Luego nosotros en nuestro algoritmo lo que hacemos es, para cada nodo distinto del origen, ver ``cuánto nos cuesta'' ponerlo entre cada par de nodos consecutivos, de cualquiera de los dos circuitos. Ver cuánto nos cuesta implica calcular el costo total de los circuitos al sacar el nodo de donde estaba y colocarlo entre cierto par de nodos consecutivos. Una vez que tenemos calculados todos los posibles movimientos de cada nodo y sus costos, nos quedamos con el mejor (siempre y cuando éste sea mejor respecto a la solución que teníamos, sino me quedo con la que tenía).

No tiene mucho sentido analizar alguno de los dos circuitos si éste tiene 4 elementos (contando dos veces el origen ya que):
\begin{compactitem}
 \item Mover alguno de los dos nodos que no son el origen en el mismo circuito no cambia nada: ORIGEN-X-Y-ORIGEN es igual a ORIGEN-Y-X-ORIGEN.
 \item Moverlo a alguna posición del otro circuito tampoco tiene mucho sentido ya que el circuito del que salió dejaría de ser un circuito válido ya que pasaría a tener 3 nodos nada más (contando dos veces el origen).
\end{compactitem}

Si pude mejorar lo que tenía, voy a volver a iterar de nuevo usando esa nueva solución como ``base''. Si no pude mejorar, entonces significa que llegué al mínimo local y termino.


\subsection{Pseudocódigo}

\begin{algorithm}[H]
\caption{\operL{BúsquedaLocal}{ \vin{inst}{InstanceResultado}, \vin{inst\_pesos}{InstanceTP3}}{IntanceResultado}}
%InstanceResultado inst, InstanceTP3 inst_pesos
\begin{algorithmic}[1]\parskip=1mm
\STATE \textit{mejorParcial} $\leftarrow$ suma de todos los pesos de los ejes de los circuitos
\STATE \textit{minimo\_local} $\leftarrow$ false
\STATE \COMMENT Mientras no alcancé el mínimo
\WHILE {$\neg$ \textit{minimo\_local}}
	\STATE \COMMENT Busco el mejor vecino
	\STATE \textit{mejorVecino} $\leftarrow$ dameElMejorVecino()
	\IF{peso de mejorParcial $>$ peso de mejorVecino}
		\STATE \COMMENT Si encontré una mejor solución que la que tenía
		\STATE \COMMENT Actualizo el resultado a esta nueva solución
		\STATE \textit{mejorParcial} $\leftarrow$ mejorVecino
		\STATE modificar los circuitos según mejorVecino
	\ELSE
		\STATE \COMMENT Si no pude mejorar, pongo minimo\_local como true y así salir dejar de iterar.
		\STATE \textit{minimo\_local} $\leftarrow$ true
	\ENDIF
\ENDWHILE
\STATE \textbf{return} \textit{mejor\_solución}

%\FOR {cada uno de los circuitos con más de 4 elementos}
%	\FOR {para cada nodo \textit{i} del circuito}
%		\STATE \COMMENT Voy a iterar por el circuito, sacando al nodo \textit{i} e ir probando donde ponerlo.
%		\STATE \textit{valor} $\leftarrow$ sacar al nodo \textit{i} del circuito y guardarlo en \textit{valor}
%		\FOR {cada uno de los circuitos}
%				\STATE \textit{w1} $\leftarrow$ primer nodo circuito
%				\STATE \textit{w2} $\leftarrow$ segundo nodo circuito
%			\WHILE{\textit{w1} no sea el último nodo del circuito}
%				\STATE \COMMENT{itero el circuito con el nodo \textit{i} removido}
%				\IF {calcularCostoDeAgregarIEntreW1yW2(\textit{valor}, \textit{w1}, \textit{w2}) $<$ \textit{mejorParcial}}
%					\STATE \COMMENT si poniendo al nodo \textit{i} entre \textit{w1} y \textit{w2} mejoro el mejor peso obtenido anteriormente:
%					\STATE \textit{mejorParcial} $\leftarrow$ nueva suma mínima
%					\STATE \textit{mejor\_solución} $\leftarrow$ modificar el circuito de la mejor solución hasta el momento con la nueva modificación
%				\ENDIF
%				\STATE avanzar en uno a \textit{w1} y \textit{w2}
%			\ENDWHILE
%		\ENDFOR
%		\STATE Vuelvo a agregar el nodo que saqué en el mismo lugar en que estaba.
%		\STATE \COMMENT Esto es simple ya que conozco su circuito original, su posición (\textit{i}) y su valor (\textit{valor}).
%	\ENDFOR
%\ENDFOR
%\STATE \textbf{return} \textit{mejor\_solución}
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 1: calcular Peso Total y asignárselo a \textit{mejorParcial}: $O(n)$
	\item Línea 2: Asignación: $O(1)$
	\item \textit{While} 4-16: Se realiza algún número finito $cant\_iteraciones$ veces.
		\begin{compactitem}
			\item Línea 6: Calcular dameElMejorVecino: $O(n^{3})$
			\item Línea 7: Pesos y comparaciones (recordar que el peso ya está calculado) $O(1)$.
			\item Línea 10-11: Asignación y modificación de los circuitos: $O(n)$
			\item Línea 14: Asignación $O(1)$
		\end{compactitem}
	\item Línea 17: Devolver la solución: $O(1)$	
	
	\item \textbf{\underline{Complejidad Final}}: Realiza $O(cant\_iteraciones)$ donde cada una cuesta $O(n^{3})$: $O(cant\_iteraciones * n^{3})$
	
	
	
%	\item \textit{For} 2-22: Se realiza una cantidad constante de veces(dos circuitos).
%		\begin{compactitem}
%
%			\item \textit{For} 3-21: Se realiza $O(n)$ veces cada uno. Pero si somos más precisos, uno se realiza $O(|tama\tilde{n}o(circuito1)|)$ y el otro $O(|tama\tilde{n}o(circuito2)|)$, y como cada nodo está en uno y sólo uno (salvo el nodo inicial, pero el cual no se itera), la suma total de iteraciones es exactamente $O(n)$.
%				\begin{compactitem}
%					\item Línea 5: Extraer el nodo requiere buscarlo $O(n)$ y sacarlo $O(1)$: $O(n)$
%					\item \textit{While} 9-17: Se realiza un total de $O(n)$ veces.
%						\begin{compactitem}
%							\item Líneas 11-15: calcularCostoDeAgregarIEntreW1yW2(): $O(n)$. Además de una comparación de enteros y una serie finita de asignaciones (poner eventualmente el nuevo circuito en la mejor solución hasta el momento).
%						\end{compactitem}
%					\item Línea 19: Agregar el nodo: $O(n)$
%				\end{compactitem}
%		\end{compactitem}
%	\item \textbf{\underline{Complejidad Final}}: $O(n)$ iteraciones en total donde en cada iteración corre otras $O(n)$ iteraciones donde cada una cuesta $O(n)$. Luego tengo $O(n^{3})$.
\end{compactitem}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operL{dameElMejorVecino}{}{MejorParcial}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \textit{mejorParcial} $\leftarrow$ 0
\FOR {$c \leftarrow$ circuito con más de 4 elementos}
	\FOR {cada nodo \textit{i} de $c$}
		\STATE \COMMENT Voy a iterar por el circuito, sacando al nodo \textit{i} e ir probando donde ponerlo.
		\STATE \textit{valor} $\leftarrow$ sacar al nodo \textit{i} del circuito y guardarlo en \textit{valor}
		\FOR {$c' \leftarrow$ circuito}
				\STATE \textit{w1} $\leftarrow$ primer nodo $c'$
				\STATE \textit{w2} $\leftarrow$ segundo nodo $c'$
			\WHILE{\textit{w1} no sea el último nodo de $c'$}
				\STATE \COMMENT{itero $c'$ con el nodo \textit{i} removido}
				\IF {calcularCostoDeAgregarIEntreW1yW2(\textit{valor}, \textit{w1}, \textit{w2}) $<$ \textit{mejorParcial} || mejorParcial == 0}
					\STATE \COMMENT si poniendo al nodo \textit{i} entre \textit{w1} y \textit{w2} mejoro el mejor peso obtenido anteriormente o es la primer vez que entro:
					\STATE \textit{mejorParcial} $\leftarrow$ nueva suma mínima
					\STATE \textit{mejor\_solución} $\leftarrow$ modificar el circuito de la mejor solución hasta el momento con la nueva modificación
				\ENDIF
				\STATE avanzar en uno a \textit{w1} y \textit{w2}
			\ENDWHILE
		\ENDFOR
		\STATE Vuelvo a agregar el nodo que saqué en el mismo lugar en que estaba.
		\STATE \COMMENT Esto es simple ya que conozco su circuito original, su posición (\textit{i}) y su valor (\textit{valor}).
	\ENDFOR
\ENDFOR
\STATE \textbf{return} \textit{mejor\_solución}
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 1: Asignación: $O(1)$
	\item \textit{For} 2-22: Se realiza una cantidad constante de veces(dos circuitos).
		\begin{compactitem}

			\item \textit{For} 3-21: Se realiza $O(n)$ veces cada uno. Pero si somos más precisos, uno se realiza $O(|tama\tilde{n}o(circuito1)|)$ y el otro $O(|tama\tilde{n}o(circuito2)|)$, y como cada nodo está en uno y sólo uno (salvo el nodo inicial, pero el cual no se itera), la suma total de iteraciones es exactamente $O(n)$.
				\begin{compactitem}
					\item Línea 5: Extraer el nodo requiere buscarlo $O(n)$ y sacarlo $O(1)$: $O(n)$
					\item \textit{While} 9-17: Se realiza un total de $O(n)$ veces.
						\begin{compactitem}
							\item Líneas 11-15: calcularCostoDeAgregarIEntreW1yW2(): $O(n)$. Además de una comparación de enteros y una serie finita de asignaciones (poner eventualmente el nuevo circuito en la mejor solución hasta el momento).
						\end{compactitem}
					\item Línea 19: Agregar el nodo: $O(n)$
				\end{compactitem}
		\end{compactitem}
	\item \textbf{\underline{Complejidad Final}}: $O(n)$ iteraciones en total donde en cada iteración corre otras $O(n)$ iteraciones donde cada una cuesta $O(n)$. Luego tengo $O(n^{3})$.
\end{compactitem}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operMA{calcularCostoDeAgregarIEntreW1yW2}{ \vin{i}{int}, \vin{v1}{int}, \vin{v2}{int}}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \textbf{var} peso $\leftarrow$ 0
\FOR {cada circuito de la solución}
	\STATE \textit{w1} $\leftarrow$ primer nodo del circuito
	\STATE \textit{w2} $\leftarrow$ segundo nodo del circuito
	\WHILE {\textit{w1} no es el último}
		\IF {\textit{w1} $==$ \textit{v1} $\land$ \textit{w2} $==$ \textit{v2}}
			\STATE \COMMENT Es decir, estoy parado entre los nodos entre los cuales debo insertar a i	
			\STATE 	Acumulo en peso la suma de las distancias de ir de \textit{w1} a i y de i a \textit{w2}
		\ELSIF {\textit{w1} == \textit{v2} $\land$ \textit{w2} $==$ \textit{v1}}
			\STATE 	Acumulo en peso la suma de las distancias de ir de \textit{w1} a i y de i a \textit{w2}
		\ELSE
			\STATE Acumulo en peso la distancia de \textit{w1} a \textit{w2}.
		\ENDIF
		\STATE avanzar en uno a \textit{w1} y \textit{w2}
	\ENDWHILE
\ENDFOR
\STATE \textbf{return} peso
\end{algorithmic}
Complejidades:
\begin{compactitem}
	\item Línea 1: Asignaciones y creaciones: $O(1)$
	\item \textit{For}: Itera 2 veces (dos circuitos).
		\begin{compactitem}
			\item Líneas 3-4: Inicializo los iteradores y avanzo: $O(1)$
			\item \textit{While} 5-15: Itero $O(n)$ en total.
				\begin{compactitem}
					\item Líneas 6-14: Comparaciones y sumas simples: $O(1)$
				\end{compactitem}
		\end{compactitem}	
	\item \textbf{\underline{Complejidad Final:}}: Itero $O(n)$ veces y cada una cuesta $O(1)$: $O(n)$
\end{compactitem}
\end{algorithm}

\subsection{Complejidad (modelo uniforme)}

La complejidad de aplicar el algoritmo de búsqueda local es $ O(cant\_iteraciones * n^{3}) $ que resulta, como se puede ver en el pseudocódigo, de aplicar % el constructor (que a su vez llama a diferentes funciones auxiliares) y obtener el resultado en $ O (1) $ con \textit{getRes}.
 la función \texttt{BúsquedaLocal} (que a su vez llama a diferentes funciones auxiliares).

La complejidad de una iteración está determinada por recorrer los $n$ nodos y para cada uno intentar ponerlo entre todos los pares consecutivos de nodos ($n$). Además, tiene que calcular el peso total para esa distribución en particular del nodo (lo que cuesta un barrido lineal de los nodos acumulando las distancias entre los nodos consecutivos ($O(n)$)). Luego nos queda $O(n * n * n) = O(n^{3})$.

Por una razón parecida a lo que ocurría en el algoritmo \texttt{Exacto}, la complejidad asintótica del mejor caso, peor caso y caso promedio de realizar una sola iteración es la misma ya que siempre vamos a analizar todas las posiciones de ambos circuitos para poner el nodo que estamos analizando en este momento, y esto hacerlo para todos los nodos.

En cuanto a la cantidad de iteraciones, ésta es intrínseca de cada grafo, no tiene relación con la cantidad de nodos ya que hay grafos donde tarda muy pocas iteraciones en encontrar el mínimo (local) y en otros puede tardar mucho.

\subsection{Demostración de la solución}

El algoritmo de búsqueda local va a terminar ya que tanto la cantidad de nodos como los pesos asociados a los ejes son finitos. Además, como siempre desciendo, en algún momento voy a llegar a un mínimo del cual no pueda salir (el cual puede ser un mínimo local o un mínimo global).

En cuanto a la solución, no tengo asegurado que sea la óptima. De hecho, en general no lo será. Lo que sí tengo asegurado es que si sacando un nodo de su circuito y agregándolo entre otros dos nodos cualesquiera puedo mejorar la solución recibida inicialmente, el algoritmo devolverá el mejor de esos movimientos. Esto se puede ver claramente en el algoritmo. Para cada nodo $v$ distinto del origen (es decir, vemos todas las posibilidades para el ``mover'') recorremos ambos circuitos en orden viendo el costo de agregar el nodo $v$ entre cada par de nodos consecutivos (con lo que nos aseguramos ver todos las posibles ``inserciones''). Luego si puedo mejorar lo que tenía, lo voy a mejorar y volver a iterar. Si no puedo mejorar, es porque llegué al mínimo (en principio local) y allí se queda.


%El algoritmo de búsqueda local va a terminar ya que la cantidad de iteraciones que hace en cada uno de los ciclos depende únicamente del tamaño de los circuitos, los cuales son finitos. Luego nunca puede pasar que itere infinitamente.

%En cuanto a la solución, no tengo asegurado que sea la óptima. De hecho, en general no lo será. Lo que sí tengo asegurado, es que si sacando un nodo de su circuito y agregándolo entre otros dos nodos cualesquiera puedo mejorar la solución recibida inicialmente, el algoritmo devolverá el mejor de esos movimientos. Esto se puede ver claramente en el algoritmo. Para cada nodo $v$ distinto del origen (es decir, vemos todas las posibilidades para el ``mover'') recorremos ambos circuitos en orden viendo el costo de agregar el nodo $v$ entre cada par de nodos consecutivos (con lo que nos aseguramos ver todos las posibles ``inserciones''). En cada iteración, me quedo con el mínimo entre el mejor movimiento que tenía y el nuevo movimiento que intenté. Hay que tener en cuenta que se remueve el nodo $v$ de su circuito (y cuando se termina de iterar con ese nodo se lo vuelve a agregar donde estaba) para no generar soluciones inválidas.

\newpage
\subsection{Tests}
%Para realizar las mediciones de los tests se usa una variable-contador insertada en el código, la cual va contando cada una de las operaciones básicas que se realizan a lo largo del algoritmo. Además se corrió por tiempo para verificar que los contadores cuentan correctamente.
%
%Además, ya que no encontramos casos patológicos para ninguno de los algoritmos, haremos los tests con un grafo con pesos random entre uno y 5000. Elegimos este número ya que llegamos a un acuerdo de que con los grafos con los que haríamos tests la diferencia en rendimiento y eficacia sería despreciable si los pesos eran mayores ya que no influencian de ninguna manera en la ejecución del algoritmo.
%
%\subsubsection{Test de Rendimiento}
%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/local1.png,width=0.9\linewidth,clip=}
%\caption{Tests de Búsqueda Local para grafos completos con distribución de pesos aleatorios.}
%\end{figure}
%
%Como fue previsto, pudimos acotar la complejidad empírica de nuestro algoritmo por la complejidad teórica previamente calculada. 

% Por otro lado, como no existe ni un mejor ni un peor caso ya que siempre tiene que revisar todas las posibilidades para mover un nodo, decidimos simplemente mostrar el resultado con un grafo (el cual siempre tiene que ser completo) con distribución de pesos aleatorio. Dicho de otra manera, cualquier grafo que elijamos va a tardar lo mismo por lo que usamos uno con distribución de pesos aleatorio.

\subsubsection{Test de Resultados}



%Decidimos testear la eficacia del algoritmo cuando reciba una \textit{buena} solución y una \textit{mala} solución. Cuando decimos buena solución nos referimos a usar el resultado de la heurística constructiva. En cambio, cuando nos referimos a una solución mala usaremos una solución obtenida con las siguientes características:
%\begin{compactitem}
% \item La longitud de ambos circuitos de la solución es random en sus intervalos posibles para que sea una solución válida.
% \item Los elementos de ambos circuitos de la solución están repartidos de forma totalmente random sin ningún tipo de prejuicios.
%\end{compactitem}
%
%De esta manera, confiamos en la gran probabilidad de que la solución obtenida sea considerablemente mala comparada con la solución de la constructiva ya que de todas las posibles soluciones válidas elegimos una al azar.
%
%\textit{Nota: para ver los resultados de la comparación entre éste y los demás algoritmos, referirse a la última sección del informe.}
%
%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/TestsFinales/TestSolLocal.png,width=0.9\linewidth,clip=}
%\caption{Análisis de resultados entre Búsqueda Local con diferentes soluciones iniciales.}
%\end{figure}
%
%-------------------------------------


Lo que quisimos mostrar en el siguiente gráfico es cómo se comporta en cada iteración el algoritmo para diferentes grafos de distintos tamaños. Como no encontramos ninguna familia de grafos que generen casos patológicos, simplemente utilizamos grafos con distribución de pesos random para los tests.

En este algoritmo, decidimos testear individualmente cómo sería el \textbf{progreso} de la solución mínima encontrada hasta el momento. Es decir, graficar los diferentes valores que va guardando como \textit{solución mínima temporal} en el código. Para ello, corrimos 8 grafos con pesos random con cantidad de nodos en parejas de dos: dos de 50, dos de 75, dos de 100 y dos de 150; siendo los 8 grafos diferentes.

Decidimos hacer este test con 8 grafos nomás para poder apreciar con más atención los pequeños detalles. De todos modos, no sacaremos conclusiones absolutas sino que analizaremos \textit{perculiaridades} que no son claras a simple vista y se cumplen con todos los grafos.



\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-BusqLoc/ProgresoBusqLoc.png,width=0.9\linewidth,clip=}
\caption{Análisis del progreso de búsqueda local con 8 entradas distintas.}
\end{figure}

En primer lugar, se puede ver que en cada iteración se mejora la solución lo que es la base de este algoritmo: siempre descender hasta encontrar el mínimo local.

Además, se puede observar que la cantidad de iteraciones que le requiere al algoritmo llegar al mínimo (local) puede variar mucho. Por ejemplo, en el \textit{grafo 1} tarda 6 iteraciones y en el \textit{grafo 8} tarda 25. Esto lo veremos mejor más adelante.

Se puede apreciar, también, el mejoramiento de la solución final con respecto a la inicial, el cual varía mucho entre cada grafo. Esto tiene que ver con que si me dan una solución inicial que está muy cerca de un mínimo local que es mucho peor que el mínimo global, indefectiblemente yo voy a caer en ese ``pozo'' y no voy a poder acercarme nunca al global. Todo depende del grafo de entrada, pero en este test podemos ver que la solución mejora considerablemente y entre soluciones temporales no hay saltos demasiado largos. Es decir, va haciendo saltos \textit{relativamente pequeños} y asumimos que es porque en el grafo random generado, no cambiaría demasiado agregar o sacar un eje, ya que la diferencia entre estos es relativamente parecida (por como está hecho, es más común cambiar un eje con peso 2500 con otro de 3500 (o con diferencias parecidas) antes que uno de 1 con otro de 4999 porque la distribución de los pesos random se asume uniforme entre los números de 1 a 5000).


\begin{figure}[H]
\centering
\epsfig{file=./graficos/TestsFinales/Solo-BusqLoc/cantitersbusqloc.png,width=0.9\linewidth,clip=}
\caption{Análisis de la cantidad de iteraciones de Busq Loc para cada n.}
\end{figure}

En este gráfico sí podemos apreciar con mayor precisión el cambio entre la cantidad de iteraciones mientras se incrementa la cantidad de nodos. Lo que hicimos fue correr grafos entre 5 y 150 nodos (con cada uno de los n entre medio de estos dos) guardándonos la cantidad de iteraciones que le llevaba a cada uno de estos 145 grafos llegar al mínimo local usando a la solución inicial mala por un lado y la constructiva como inicial por otro.

No es sorprendente que le lleve más iteraciones con la inicial mala ya que tiene menos \textit{ventana de mejoramiento}, por así decirlo, y va a poder mejorar más la solución antes de trabarse con el mínimo local. En el caso de que recibe la constructiva como inicial, ya que la constructiva de por sí encuentra una solución \textit{buena}, le cuesta más a la búsqueda local mejorarla y por ende 

%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/local1.png,width=0.9\linewidth,clip=}
%\caption{Tests seguimiento de iteraciones de Búsqueda Local para grafos completos con distribución de pesos aleatorios.}
%\end{figure}




%Decidimos testear la eficacia del algoritmo cuando reciba una \textit{buena} solución y una \textit{mala} solución. Cuando decimos buena solución nos referimos a usar el resultado de la heurística constructiva. En cambio, cuando nos referimos a una solución mala usaremos una solución obtenida con las siguientes características:
%\begin{compactitem}
% \item La longitud de ambos circuitos de la solución es random en sus intervalos posibles para que sea una solución válida.
% \item Los elementos de ambos circuitos de la solución están repartidos de forma totalmente random sin ningún tipo de prejuicios.
%\end{compactitem}
%
%De esta manera, confiamos en la gran probabilidad de que la solución obtenida sea considerablemente mala comparada con la solución de la constructiva ya que de todas las posibles soluciones válidas elegimos una al azar.
%
%\textit{Nota: para ver los resultados de la comparación entre éste y los demás algoritmos, referirse a la última sección del informe.}
%
%\begin{figure}[H]
%\centering
%\epsfig{file=./graficos/TestsFinales/TestSolLocal.png,width=0.9\linewidth,clip=}
%\caption{Análisis de resultados entre Búsqueda Local con diferentes soluciones iniciales.}
%\end{figure}
%
%%El grafo muestra un resultado sorprendente: la suma de las soluciones de la búsqueda local con solución inicial \textit{mala} parece crecer de forma lineal acorde aumenta la cantidad de nodos en el grafo. En cambio, en el caso de la solución \textit{buena} parece ser un crecimiento logarítmico o casi constante. Faltarían más pruebas para poder afirmar algo concreto, pero algo es seguro: no lo esperábamos.
%Como se puede ver cuanto más grande es el grafo peor es la solución mala y más le cuesta mejorarla al algoritmo de búsqueda local. Otra forma de verlo es que cuantos más nodos hay, menor es el porcentaje que se puede mejorar moviendo un solo nodo ya que el peso de variar tres ejes en un grafo que tiene, por decir, cincuenta, es considerablemente menor al de uno que tiene diez.
%
%% \begin{figure}[H]
%% \centering
%% \epsfig{file=./graficos/graficoBusquedaLocalvsExacto.jpg,width=0.9\linewidth,clip=}
%% \caption{Análisis de resultados entre Búsqueda Local y el algoritmo Exacto.}
%% \end{figure}
%% 
%% La idea de este gráfico es mostrar cómo se mejora una solución inicial dada al aplicar la heurística de Búsqueda Local. Lo que hicimos fue generar diferentes soluciones iniciales aleatorias, y a todas aplicarles el algoritmo de búsqueda local, siempre para el mismo grafo. Como se puede ver, en promedio mejora alrededor de un 50\% con respecto a la solución inicial. Incluso en uno de los casos, alcanza la solución óptima.